Jan 96 Challenge
- Feb 96 Challenge
- Mar 96 Challenge
- Apr 96 Challenge
- May 96 Challenge
- Jun 96 Challenge
- Jul 96 Challenge
- Aug 96 Challenge
- Sep 96 Challenge
- Oct 96 Challenge
- Nov 96 Challenge
- Dec 96 Challenge
Volume Number: 12
Issue Number: 1
Column Tag: Programmer’s Challenge
Programmer’s Challenge 
By Bob Boonstra, Westford, Massachusetts
Note: Source code files accompanying article are located on MacTech CD-ROM orsource code disks.
Sliding Tiles
You have all probably seen small versions of the puzzle that is the basis for this
month’s Challenge: a 4-by-4 grid of interlocking tiles, with one empty tile among the
16 cells allowing the puzzle to be scrambled by sliding adjacent cells into the empty
location. This month the Challenge is to write code that will unscramble a larger
version of the Sliding Tiles puzzle.
The prototype for the code you should write is:
typedef Boolean /*legalMove*/ (*MoveProc)(
/* Callback procedure to move tile at */
long tileToMoveRow, /* these coordinates into the location */
long tileToMoveCol /* of adjacent empty tile */
);
void SolveTiles(
long *tiles, /* pointer to array of tiles where */
long numRows, /* tile (row,col) is at */
long numCols, /* *(tiles + row*numCols + col) */
MoveProc MakeMove /* Callback procedure to move a tile */
);
You will be given a pointer tiles into an array of tile values, the number of
rows and columns in the puzzle (numRows and numCols, respectively), and the address
of a callback procedure MakeMove used to tell my test code about the moves you make to
solve the puzzle. The tiles array will be initialized with the values
0..numRows*numCols-1, in an order scrambled by the calling routine. The value 0
represents the empty tile.
Your code should make a sequence of calls to MakeMove and return when the
puzzle is solved. Each MakeMove call exchanges the empty tile with the indicated
adjacent tile. The puzzle is solved when you have moved each tile into its proper
location: moving the tile with value i into location tiles[i] (i.e., row=i/numCols and
col=i%numCols).
The callback routine will be something like the code provided below:
static long gNumRows,gNumCols; /* initialized by test code */
static long gEmptyRow,gEmptyCol; /* initialized by test code */
static long *gTiles; /* initialized by test code */
#define TileValue(tiles,row,col) *(tiles+(row)*gNumCols+(col))
#define OutOfRange(val,num) (((val)<0) || ((val)>=(num)))
static Boolean MakeMove(long tileToMoveRow,long tileToMoveCol)
{
long diff;
if (OutOfRange(tileToMoveRow,gNumRows)) return false;
if (OutOfRange(tileToMoveCol,gNumCols)) return false;
if (tileToMoveRow == gEmptyRow) {
diff = tileToMoveCol - gEmptyCol;
} else if (tileToMoveCol == gEmptyCol) {
diff = tileToMoveRow - gEmptyRow;
} else {
return false;
}
if ((diff != -1) && (diff != 1)) return false;
TileValue(gTiles,gEmptyRow,gEmptyCol) =
TileValue(gTiles,tileToMoveRow,tileToMoveCol);
gEmptyRow = tileToMoveRow;
gEmptyCol = tileToMoveCol;
TileValue(gTiles,gEmptyRow,gEmptyCol) = 0;
}
As an example, given the initial conditions:
long tiles[] = {1,4,0,3,5,2};
SolveTiles(tiles,2,3,MakeMove);
you could generate the following moves:
MakeMove(1,2);
MakeMove(1,1);
MakeMove(0,1);
MakeMove(0,0);
to transform the puzzle like this: